<html>
<head>
	<meta charset="UTF-8">
	<meta content="IE=edge" http-equiv="X-UA-Compatible">
	<meta content="initial-scale=1.0, maximum-scale=1.0, user-scalable=no, width=device-width" name="viewport">
	<title>4481：[Jsoi2015]非诚勿扰</title>
	<!-- css -->
	<link href="../css/base.min.css" rel="stylesheet">
	<link href="../css/project.min.css" rel="stylesheet">
	
	<!-- favicon -->
	<!-- ... -->
</head>
<body class="page-brand">
	<header class="header header-transparent header-waterfall ui-header">
		<ul class="nav nav-list pull-left">
			<li>
				<a data-toggle="menu" href="#menu">
					<span class="icon icon-lg">menu</span>
				</a>
			</li>
		</ul>
		<a class="header-logo header-affix-hide margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[Jsoi2015]非诚勿扰</a>
		<span class="header-logo header-affix margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[Jsoi2015]非诚勿扰</span>
	</header>
	<nav aria-hidden="true" class="menu" id="menu" tabindex="-1">
		<div class="menu-scroll">
			<div class="menu-content">
				<a class="menu-logo" href="../index.html">BZOJ离线题库</a>
				<ul class="nav">
					<li>
						<a class="waves-attach" data-toggle="collapse" href="#problems">题目</a>
						<ul class="menu-collapse collapse in" id="problems">
							<li>
								<a class="waves-attach" href="../index.html">主页</a>
							</li>
							<li>
								<a class="waves-attach" href="../list.html">题目列表</a>
							</li>
						</ul>
					</li>
					<li>
						<a class="collapsed waves-attach" data-toggle="collapse" href="#about">关于</a>
						<ul class="menu-collapse collapse" id="about">
							<li>
								<a class="waves-attach" href="../about.html">关于此项目</a>
							</li>
						</ul>
					</li>
					
				</ul>
			</div>
		</div>
	</nav>
	<main class="content">
		<div class="content-header ui-content-header">
			<div class="container">
				<h1 class="content-heading">
                [Jsoi2015]非诚勿扰                </h1>
                <p>时间限制：20s&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  空间限制：512MB</p>			</div>
		</div>
		<div class="container">
			<section class="content-inner margin-top-no">
				<div class="row">
					<div class="col-lg-13 col-md-13">
						<div class="card margin-bottom-no">
							<div class="card-main">
								<div class="card-inner">
									
                                <h3>题目描述</h3><p><p>【故事背景】<br />
JYY赶上了互联网创业的大潮，为非常勿扰开发了最新的手机App实现单身<br />
大龄青年之间的&ldquo;速配&rdquo;。然而随着用户数量的增长，JYY发现现有速配的算法似<br />
乎很难满足大家的要求，因此JYY决定请你来调查一下其中的原因。<br />
【问题描述】<br />
应用的后台一共有N个女性和M个男性，他们每个人都希望能够找到自己的<br />
合适伴侣。为了方便，每个男性都被编上了1到N之间的一个号码，并且任意两<br />
个人的号码不一样。每个女性也被如此编号。<br />
JYY应用的最大特点是赋予女性较高的选择权，让每个女性指定自己的&ldquo;如<br />
意郎君列表&rdquo;。每个女性的如意郎君列表都是所有男性的一个子集，并且可能为<br />
空。如果列表非空，她们会在其中选择一个男性作为自己最终接受的对象。<br />
JYY用如下算法来为每个女性速配最终接受的男性：将&ldquo;如意郎君列表&rdquo;中的<br />
男性按照编号从小到大的顺序呈现给她。对于每次呈现，她将独立地以P的概率<br />
接受这个男性（换言之，会以1&minus;P的概率拒绝这个男性）。如果她选择了拒绝，<br />
App就会呈现列表中下一个男性，以此类推。如果列表中所有的男性都已经呈现，<br />
那么中介所会重新按照列表的顺序来呈现这些男性，直到她接受了某个男性为止。<br />
显然，在这种规则下，每个女性只能选择接受一个男性，而一个男性可能被多个<br />
女性所接受。当然，也可能有部分男性不被任何一个女性接受。<br />
这样，每个女性就有了自己接受的男性（&ldquo;如意郎君列表&rdquo;为空的除外）。现<br />
在考虑任意两个不同的、如意郎君列表非空的女性a和b，如果a的编号比b的编<br />
号小，而a选择的男性的编号比b选择的编号大，那么女性a和女性b就叫做一对<br />
不稳定因素。<br />
由于每个女性选择的男性是有一定的随机性的，所以不稳定因素的数目也是<br />
有一定随机性的。JYY希望你能够求得不稳定因素的期望个数（即平均数目），<br />
从而进一步研究为什么速配算法不能满足大家的需求。</p></p><hr/><h3>输入格式</h3><p><p>输入第一行包含2个自然数N,M，表示有N个女性和N个男性，以及所有女<br />
性的&ldquo;如意郎君列表&rdquo;长度之和是M。<br />
接下来一行一个实数P，为女性接受男性的概率。<br />
接下来M行，每行包含两个整数a,b，表示男性b在女性a的&ldquo;如意郎君列表&rdquo;<br />
中。<br />
输入保证每个女性的&ldquo;如意郎君列表&rdquo;中的男性出现切仅出现一次。<br />
1&le;N,M&le;500,000，0.4&le;P&lt;0.6</p></p><hr/><h3>输出格式</h3><p><p>输出1行，包含一个实数，四舍五入后保留到小数点后2位，表示不稳定因素的期望数目。</p></p><hr/><h3>样例输入</h3><pre>5 5
0.5
5 1
3 2
2 2
2 1
3 1</pre><hr/><h3>样例输出</h3><pre>0.89</pre><hr/><h3>提示</h3><p>没有写明提示</p><hr/><h3>题目来源</h3><p>By 佚名上传</p>
								</div>
							</div>
						</div>
					</div>
				</div>
				
				
			</section>
		</div>
	</main>

	<div class="fbtn-container">
		<div class="fbtn-inner">
			<a class="fbtn fbtn-lg fbtn-brand-accent waves-attach waves-circle waves-light waves-effect" data-toggle="dropdown" aria-expanded="true"><span class="fbtn-text fbtn-text-left">Menu</span><span class="fbtn-ori icon">apps</span><span class="fbtn-sub icon">close</span></a>
			<div class="fbtn-dropup">
				<a class="fbtn fbtn-brand waves-attach waves-circle waves-light waves-effect" href="../list.html" target="_self"><span class="fbtn-text fbtn-text-left">题目列表</span><span class="icon">menu</span></a>
				<a class="fbtn fbtn-green waves-attach waves-circle waves-effect" href="../index.html" target="_self"><span class="fbtn-text fbtn-text-left">返回主页</span><span class="icon">home</span></a>
				<a class="fbtn waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/submitpage.php?id=4481" target="_blank"><span class="fbtn-text fbtn-text-left">提交代码</span><span class="icon">send</span></a>
				<a class="fbtn fbtn-orange waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/wttl/wttl.php?pid=4481" target="_blank"><span class="fbtn-text fbtn-text-left">试题讨论</span><span class="icon">chat</span></a>
				
			</div>
		</div>
	</div>

	<!-- js -->
	<script src="../js/jquery.min.js"></script>
	<script src="../js/base.min.js"></script>
	<script src="../js/project.min.js"></script>
</body>
</html>